package JZ_Offer.algorithm.dp;

/**
 * 矩形覆盖
 * <p>
 * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
 * <p>
 * 动态规划  要找规律和临界点
 * 分析：设方法为n的函数 f(n)
 * n=0 没有小矩形可以摆放 所以 f(0)=0
 * n=1 只能横着摆放 所以 f(1)=1
 * n=2 可以横着竖着摆放一个小矩形 f(2)=2
 * n=3时：
 * --第3级横着摆放 用1级 剩2级 有f(3-1)种方法
 * --第3级竖着摆放 用2级 剩1级 有f(3-2)种方法
 * --两种方式都考虑 有 f(3-1) + f(3-2) 种方法
 * 规律：当n>2时 第n级等于前两级的和 2为临界点
 * 是一个斐波那契额数列 求斐波那契第n项的值
 *
 * @Author piper
 * @Date 2019/11/19 10:36 上午
 */
public class JZ70_矩形覆盖 {

    private static int RectCover(int n) {
        if (n <= 1) {
            return n;
        }
        return RectCover(n - 1) + RectCover(n - 2);
    }

    private static int RectCover1(int target) {
        if (target < 3) return target;
        int[] cover = new int[target + 1];
        cover[0] = 0;
        cover[1] = 1;
        cover[2] = 2;
        for (int i = 3; i <= target; i++) {
            cover[i] = cover[i - 1] + cover[i - 2];
        }
        return cover[target];
    }

    private static int RectCover2(int target) {
        int l1 = 1, l2 = 2, res = 0;
        for (int i = 3; i <= target; i++) {
            res = l2 = l2 + l1;
            l1 = l2 - l1;
        }
        return res;
    }

    private static int RectCover3(int target) {
        int l1 = 1, l2 = 2;
        for (int i = 3; i <= target; i++) {
            l2 = l2 + l1;
            l1 = l2 - l1;
        }
        return l2;
    }

    public static void main(String[] args) {
        System.out.println(RectCover3(7));
    }
}
